#coding: utf-8
def arrange(nowState,desiredState):
    """
    move that only can be moved,
    and neededExchange became less and less when moving
    """
    couldExchange={}
    neededExchange={}
    for state in nowState:
        if not state.get("locked"):
            couldExchange[state["slotId"]]=state["bookName"]
            if state["bookName"]:
                neededExchange[state["bookName"]]=state["slotId"]
    desiredStateDict={}
    for state in desiredState:
        if state["bookName"]:
            desiredStateDict[state["bookName"]]=state["slotId"]
    while neededExchange:
        bookName,slotId=neededExchange.popitem()
        newSlotId=desiredStateDict.pop(bookName)
        if slotId!=newSlotId:
            try:
                thatBookName=couldExchange.pop(newSlotId)
            except:
                couldExchange.pop(slotId)
            else:
                print 'soltId %d in exchange of soldId %d'%(slotId,newSlotId)
                if thatBookName:
                    neededExchange[thatBookName]=slotId
                couldExchange[slotId]=thatBookName

if __name__=='__main__':
    #simulate State
    import random
    def getRandomState ():
        #contruct 100 empty slots
        randomState=[]
        for i in xrange(100):
            state={}
            state["slotId"]=i+1
            state["bookName"]=""
            state["locked"]=False
            randomState.append(state)
        #put 70 books in them
        n=1
        for i in random.sample(range(0,100),70):
            randomState[i]["bookName"]='name%d'%n
            n+=1
        return randomState
    desiredState=getRandomState()
    nowState=getRandomState()
    #Suppose if there 10 books be borrowed when making arrange plan
    notEmpty=[]
    for i,state in enumerate(nowState):
        if state["bookName"]:
            notEmpty.append(i)
    for i in random.sample(notEmpty,10):
        nowState[i]["locked"]=True
    
    arrange(nowState,desiredState)

    print
    print "Another Test"
    arrange([{"slotId": 1, "bookName": "a"}, \
         {"slotId": 2, "bookName": ""}, \
         {"slotId": 3, "bookName": "b"}, \
         {"slotId": 4, "bookName": "c","locked":True}, \
         {"slotId": 5, "bookName": ""}, \
         {"slotId": 6, "bookName": "d"}] \
        ,[{"slotId": 1, "bookName": "c"}, \
         {"slotId": 2, "bookName": "d"}, \
         {"slotId": 3, "bookName": ""}, \
         {"slotId": 4, "bookName": "b"}, \
         {"slotId": 5, "bookName": "a"}, \
         {"slotId": 6, "bookName": ""}] )